#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n;
int l[N], r[N];//存二叉树

void dfs1(int root)
{
	cout << root << " ";
	if(l[root]) dfs1(l[root]);
	if(r[root]) dfs1(r[root]);
}

void dfs2(int root)
{
	if(l[root]) dfs2(l[root]);
	cout << root << " ";
	if(r[root]) dfs2(r[root]);
}

void dfs3(int root)
{
	if(l[root]) dfs3(l[root]);
	if(r[root]) dfs3(r[root]);
	cout << root << " ";
}

int main()
{
	cin >> n;
	//建树
	for(int i = 1; i <= n; i++)
	{
		cin >> l[i] >> r[i];
	}

	dfs1(1);//前序遍历
	cout << endl;
	dfs2(1);//中序遍历
	cout << endl;
	dfs3(1);//后序遍历
	cout << endl;

	return 0;
}
